//给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。 
//
// 注意：请不要在超过该数组长度的位置写入元素。 
//
// 要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。 
//
// 
//
// 示例 1： 
//
// 输入：[1,0,2,3,0,4,5,0]
//输出：null
//解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
// 
//
// 示例 2： 
//
// 输入：[1,2,3]
//输出：null
//解释：调用函数后，输入的数组将被修改为：[1,2,3]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= arr.length <= 10000 
// 0 <= arr[i] <= 9 
// 
// Related Topics 数组 双指针 👍 145 👎 0

package leetcode.editor.cn;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class _1089_DuplicateZeros {
    public static void main(String[] args) {
        Solution solution = new _1089_DuplicateZeros().new Solution();
        int[] nums = {8, 4, 5, 0, 0, 0, 0, 7};
        solution.duplicateZeros(nums);
        System.out.println(Arrays.toString(nums));
    }

    class Solution {
        public void duplicateZeros(int[] arr) {
            int len = arr.length;
            int top = 0;
            int i = 0;
            while (top < len) {
                if (arr[i++] != 0) {
                    top++;
                } else {
                    top += 2;
                }
            }

        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution1 {
        public void duplicateZeros(int[] arr) {
            Deque<Integer> stack = new ArrayDeque<>();
            for (int i = 0; i < arr.length && stack.size() < arr.length; i++) {
                if (arr[i] != 0) {
                    stack.push(arr[i]);
                } else {
                    stack.push(0);
                    if (stack.size() < arr.length - 1)
                        stack.push(0);
                }
            }
            for (int i = arr.length - 1; i >= 0; i--) {
                arr[i] = stack.pop();
            }
            return;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}